This subproject is one of many research subprojects utilizing the resources provided by a Center grant funded by NIH/NCRR. The subproject and investigator (PI) may have received primary funding from another NIH source, and thus could be represented in other CRISP entries. The institution listed is for the Center, which is not necessarily the institution for the investigator. Abstract: The proposed research applies and investigates graph polynomials in three closely related areas: string reconstructions, DNA constructs in biomolecular computing, and structural theory for the parameterized Tutte, topological Tutte, and generalized transition polynomials. I will be focusing my research on three topics, the first two involving applications of graph polynomials, and the last building theoretical foundations of graph polynomials. I will use relations among the interlace and generalized transition polynomials and various generalizations of the Tutte polynomial to address the general question of reconstructing strings of data from sets of substrings, a problem initially motivated by DNA sequencing. I will use the generalized transition and topological Tutte polynomials, results from cycle double coverings, and tools from topological graph theory to inform DNA constructs at the heart of combinatorial biomolecular computing. These applications are dependent on theoretical results concerning the properties and underlying algebraic structures of graph polynomials, so I will also continue on-going foundational work on the structural properties of a variety of graph and matroid functions. Significance: This research in the field of bioinformatics seeks theoretical information to inform critical areas of biomedical research. The significance of this work will be manifest in its impact in two areas of bioinformatics: DNA sequencing by hybridization and the construction of DNA nanostructures pursuant to pharmaceutical applications and biomolecular computing. Both of these areas are of current critical interest in the field of bioinformatics. Improved methods for DNA sequencing will lead to more efficient identifications of DNA properties, and more efficient techniques for reading long strings of DNA. One of the current challenges in the highly promising area of biomolecular computing is encoding the mathematical concepts into DNA structures that then may be subject to biological processes which accomplish complex computational algorithms. The significance of this research is that it will provide theoretical tools for manifesting those mathematical structures as DNA nano-constructs which may then be subjected to biological processes that affect the necessary computations without the exponential time constraints of a digital computer. Furthermore, these DNA nano-structures, if rigidly constructed, have potential to be used as delivery mechanisms for other biological agents such as proteins within the body, as well other applications in the fast moving field of nano-technology.